package com.lun.swordtowardoffer2.c15;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class FindOrder {

	public int[] findOrder(int numCourses, int[][] prerequisites) {
		Map<Integer, List<Integer>> graph = new HashMap<>();
		
		for(int i = 0; i < prerequisites.length; i++) {
			graph.put(i, new ArrayList<>());
		}
		
		int[] inDegrees = new int[numCourses];
		for(int[] prerequisite : prerequisites) {
			inDegrees[prerequisite[0]]++;
			graph.get(prerequisite[1]).add(prerequisite[0]);
		}
		
		Queue<Integer> queue = new LinkedList<>();
		for(int i = 0; i < numCourses; i++) {
			if(inDegrees[i] == 0) {
				queue.offer(i);
			}
		}
		
		List<Integer> order = new ArrayList<>();
		while(!queue.isEmpty()) {
			int course = queue.poll();
			order.add(course);
			for(int next : graph.get(course)) {
				if(--inDegrees[next] == 0) {
					queue.offer(next);
				}
			}
		}
		
		return order.size() == numCourses ? //
				order.stream().mapToInt(i->i).toArray() : new int[0];
	}
	
}
